package com.midea.leetcode;

import javax.swing.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @description：
 * @author: wangwl23
 * N皇后问题
 * @create: 2021-03-10 10:42
 */
public class NQueen {
    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(8);
        System.out.println(lists);
    }
    public static List<List<String>> solveNQueens(int n) {
        char[][] chess = new char[n][n];
        for(int i= 0;i<n;i++){
            for (int j =0 ;j<n;j++){
                chess[i][j] = '.';
            }
        }
        List<List<String>> res = new ArrayList<>();
        solve(res,chess,0);
        return res;
    }

    private static void solve(List<List<String>> res, char[][] chess, int row) {
        if(row == chess.length){
            res.add(construct(chess));
            return;
        }
        for (int col=0;col<chess.length;col++){
            if(valid(chess,row,col)){
                chess[row][col] = 'Q';
                solve(res, chess,row+1);
                chess[row][col] = '.';
            }
        }
    }

    private static boolean valid(char[][] chess, int row, int col) {
        for (int i= 0;i<row;i++){
            if(chess[i][col] == 'Q'){
                return false;
            }
        }
        for (int i=row-1,j=col+1;i>=0&&j<chess.length;i--,j++){
            if(chess[i][j] == 'Q'){
                return false;
            }
        }
        for (int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(chess[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }

    public static List<String> construct(char[][] chess){
        List<String> path = new ArrayList<>();
        for(int i= 0;i<chess.length;i++){
            path.add(new String(chess[i]));
        }
        return path;
    }
}
